package sword.chapter2Array;

import java.util.HashMap;

/**
 * 和为k的子数组
 * 输入一个整数数组和一个整数k，请问数组中有多少个数字之和等于k的连续子数组？例如输入数组[1, 1, 1]，k的值为2，有2个连续子数组之和等于2。
 * <p>
 * 累加数组
 * 1. Si Sj当做一个整体
 * 2. 记录Si出现次数
 *
 * @author K
 * @date 2021-11-02 21:02
 */
public class S10SubarraySum {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 1, 1, 2, 2, 1, 1};
        int result = s10SubarraySum(nums, 3);
        int result2 = s10SubarraySum2(nums, 3);
        System.out.println();
    }

    public static int s10SubarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        // 0出现过一次
        map.put(0, 1);
        for (int num : nums) {
            // Si = x 前i个数之和sum，并在后面记录sum出现的次数。如果都是整数，那么sum都只出现1次。如果有负数，sum会出现多次
            sum += num;
            // Sj = x - k 前j个数之和。此时的Si是整体，Sj是前半截（可能是历史的Si），k是后半截。如果存在Sj，那么后半截连续数组出现了和为k
            count += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

    /**
     * 只适用于正整数
     */
    public static int s10SubarraySum2(int[] nums, int k) {
        int left = 0;
        int count = 0;
        int sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (left <= right && sum >= k) {
                if (sum == k) {
                    count++;
                }
                sum -= nums[left++];
            }
        }
        return count;
    }
}
